The present invention relates generally to output devices and more specifically to halftoning.
According to the Postscript Language Reference Manual, “[h]alftoning is a process by which continuous tone colors are approximated on an output device that can achieve only a limited number of discrete colors. Colors that the device cannot produce directly are simulated by using patterns of pixels in the colors available.”
Some output devices can reproduce continuous-tone colors directly. Halftoning is not required for such devices. After gamma correction by the transfer functions, the color components are transmitted directly to the device. On devices that do require halftoning, it occurs after all color components have been transformed by the applicable transfer functions. The input to the halftone function consists of continuous tone gamma-corrected color components in the device's native color space. Its output consists of pixels in colors that the device can reproduce.
Halftones are a device dependent mechanism used to allow users of devices with a relatively small number of colors and/or low resolution to exercise fine control over how colors and grays appear when output. They are sometimes used to implement special effects (such as patterns) as well.
Halftones are defined in PostScript using the notion of a halftone screen, which divides an array of device pixels (an area on the screen) into cells which may be modified to produce the desired halftone effects. Each device pixel belongs to one cell of the screen; a single cell typically contains many pixels. On a black and white device, each cell can be made to simulate a given value of gray by producing some of the cell's device pixels black and others white. Numerically, the gray level produced is the relation between the area of the cell which is white to the total area of the cell. Unfortunately, this is not necessarily the relation between the number of white pixels and the number of pixels in the cell because of common interactions between bits of ink and how the ink is made to stick to the page.
The above description also applies to color devices whose pixels consist of colorants that are either completely on or completely off. Most color printers, but not color displays, work this way. Halftoning is applied to each color component independently, producing shades of that color. The need to control interactions between the color screens for each component is a major part of why many users demand a high level of control over the halftoning process.
In general, Postscript Halftones are defined in one of two ways: 1) a frequency, angle and spot function combination; or 2) with a threshold array. The first method mimics the method found in classical photographic processes wherein each halftone cell is conceived of as a region of the screen which is colored by a “spot” whose size and shape is specified by the spot function. The size and position of each cell is defined by the frequency and angle supplied. With digital devices, a complication occurs when trying to determine which image pixels to go which halftone cell. Selecting which ones to color for a given shade of gray is essentially arbitrary. This exacerbates any problems due to “beat” patterns when using different halftone colors to overlay each other.
A threshold array assumes a fixed size for the halftone cells, and defines exactly which ones to color for a given shade of gray. An advantage of threshold arrays is that it is very simple to represent them as a region of memory on a computer. They may be efficiently rendered on such devices as well. A drawback of a threshold array is that it can be difficult to exactly represent screens at arbitrary angles or with non-square spot shapes due to shapes not lining up accurately with the device pixel grid. Postscript defines Halftone types 10 and 16 to allow the description of screens at arbitrary rational angles, but at the expense of making the rectangular region of memory needed to represent them accurately being very large. As a result, many existing systems use methods to approximate these halftones. As a result, Postscript halftone types 10 and 16 are often not rendered exactly using a threshold array.
The Type 10 halftone addresses the difficulty of representing halftone cells at arbitrary angles by dividing the cell into a pair of squares of different sizes. As a result, determining quickly what pixel of the halftone cell should be colored by a given device pixel has proven to be a time-consuming task. The squares are much easier to store and specify than a threshold map would be if stored at an angle, although they present challenges to some rendering engines. Type 16 halftones are similar to type 10 halftones, except that the two squares are more generalized as two arbitrary sized rectangles.
Existing implementations of these types of halftone cells determine whether and how a given device pixel should be colored by calculating the pixel's location within the squares (or rectangles). If the pixel's location is outside the (X,Y) coordinates of those squares (or rectangles) when centered at the page's origin, some existing implementations subtract the horizontal and vertical displacements between cells repeatedly until the pixel is within the cell's area. Other implementations simply approximate the pixel's location as a larger square (or rectangle) that overlaps itself. However, both of these implementations are slow due to repeated calculations of either the duplicated pixels or due to the iterative stepping towards the origin until valid coordinates are reached. In addition, the “large rectangle” implementation has the drawback that the large rectangle does not line up on the same device pixels as the type 10 cells would, yielding artifacts around the edges of the cells.